#include "biTree.h"
#include "../linkstack/linkstack.h"

extern func_LinkStack fLinkStack;

/**
 * 功 能：
 *      二叉树的递归遍历 - 后序遍历
 * 参 数：
 *      root：要遍历的树
 * 返回值：
 *      无 
 **/
void Traversal_Later(BiTNode *root)
{
    if (root == NULL)
        return;

    // 遍历左子树
    Traversal_Later(root->lchild);
    // 遍历右子树
    Traversal_Later(root->rchild);
    // 遍历根节点
    printf("%c ", root->data);
}

/**
 * 功 能：
 *      二叉树的递归遍历 - 类似于先序遍历
 *      遍历的顺序为 ： 根节点 -> 右子树 -> 左子树
 * 参 数：
 *      root：要遍历的树
 * 返回值：
 *      无 
 **/
void Traversal_rrl(BiTNode *root)
{
    if (root == NULL)
        return;

    // 遍历根节点
    printf("%c ", root->data);
    // 遍历右子树
    Traversal_rrl(root->rchild);
    // 遍历左子树
    Traversal_rrl(root->lchild);
}

void nonTraversal_PostOrder(BiTNode *root);
void postOrder_Root_Right_Left_Array(BiTNode *root);
void postOrder_Root_Right_Left_Stack(BiTNode *root);
/**
 * 功 能：
 *      创建并且初始二叉树 - 指针定义
 * 参 数：
 *      无
 * 返回值：
 *      无
 **/
void BiTree_Create(void)
{
    BiTNode *p1, *p2, *p3, *p4, *p5, *p6, *p7, *p8, *p9;

    p1 = (BiTNode *)malloc(sizeof(BiTNode));
    p2 = (BiTNode *)malloc(sizeof(BiTNode));
    p3 = (BiTNode *)malloc(sizeof(BiTNode));
    p4 = (BiTNode *)malloc(sizeof(BiTNode));
    p5 = (BiTNode *)malloc(sizeof(BiTNode));
    p6 = (BiTNode *)malloc(sizeof(BiTNode));
    p7 = (BiTNode *)malloc(sizeof(BiTNode));
    p8 = (BiTNode *)malloc(sizeof(BiTNode));
    p9 = (BiTNode *)malloc(sizeof(BiTNode));

    memset(p1, 0, sizeof(BiTNode));
    memset(p2, 0, sizeof(BiTNode));
    memset(p3, 0, sizeof(BiTNode));
    memset(p4, 0, sizeof(BiTNode));
    memset(p5, 0, sizeof(BiTNode));
    memset(p6, 0, sizeof(BiTNode));
    memset(p7, 0, sizeof(BiTNode));
    memset(p8, 0, sizeof(BiTNode));
    memset(p9, 0, sizeof(BiTNode));

    p1->data = 'A';
    p2->data = 'B';
    p3->data = 'C';
    p4->data = 'D';
    p5->data = 'E';
    p6->data = 'F';
    p7->data = 'G';
    p8->data = 'H';
    p9->data = 'I';

    /* 二叉树的关系式的创建 */
    p1->lchild = p2;
    p1->rchild = p3;
    p2->lchild = p4;
    p2->rchild = p5;
    p3->lchild = p6;
    p3->rchild = p7;
    p4->lchild = p8;
    p4->rchild = p9;

    /* 二叉树的遍历 */
    printf("Traversal_post : ");
    Traversal_Later(p1);
    putchar(10);

    // printf("Traversal-2 : ");
    // Traversal_rrl(p1);
    // putchar(10);

    printf("traversal.post : ");
    traversal.post(p1);
    putchar(10);

    printf("nonTraversal_PostOrder : ");
    nonTraversal_PostOrder(p1);
    putchar(10);

    printf("nonTraversal_RRL_Array : ");
    postOrder_Root_Right_Left_Array(p1);
    putchar(10);
    printf("nonTraversal_RRL_Stack : ");
    postOrder_Root_Right_Left_Stack(p1);
    putchar(10);

    printf("%s Finished! \n", __func__);
}

/**
 * 功 能：
 *      二叉树的非递归遍历 - 先序遍历
 * 参 数：
 *      root：要遍历的树
 * 返回值：
 *      无 
 **/
void nonTraversal_Before(BiTNode *root)
{
    if (root == NULL)
        return;
}

/**
 * 功 能：
 *      二叉树的非递归遍历 - 中序遍历
 * 参 数：
 *      root：要遍历的树
 * 返回值：
 *      无 
 **/
void nonTraversal_Middle(BiTNode *root)
{
    if (root == NULL)
        return;
}

/**
 * 功 能：
 *      二叉树的非递归遍历 - 后序遍历
 * 参 数：
 *      root：要遍历的树
 * 返回值：
 *      无 
 **/
void nonTraversal_Post(BiTNode *root)
{
    if (root == NULL)
        return;
    // 创建一个栈
    LinkStack *stack = fLinkStack.create();
    BiTNode *top = NULL, *temp = NULL;

    // 节点存在并且栈不为空
    while (root || fLinkStack.length(stack) > 0)
    {
        // 节点存在
        while (root) // 从当前节点开始判断是否存在左孩子，一直到最后一个左孩子节点
        {
            // 将当前节点入栈
            fLinkStack.push(stack, (LinkStackNode *)root);
            // 将指针指向左孩子节点，然后判断是否存在左孩子
            root = root->lchild;
        }

        // 左孩子不存在，此时获取栈顶元素，根据栈顶元素进行下一步
        top = fLinkStack.top(stack);

        // 判断是否存在右孩子
        // 或者栈顶元素的右孩子与出栈的元素相同
        if (top->rchild == NULL || top->rchild == temp)
        {
            // 如果不存在右孩子，则说明此节点为叶子节点，将节点值打印
            printf("%c ", top->data);
            // 将此节点出栈，并记录下来用作下次栈顶元素的右孩子的判断
            // 用于判断是从左孩子回退的还是右孩子回退的
            temp = fLinkStack.pop(stack);
        }
        else
        {
            // 将指针指向右孩子节点，然后重新开始判断
            root = top->rchild;
        }
    }
    // 销毁栈
    fLinkStack.destroy(stack);
}
/**
 * 功 能：
 *      二叉树的非递归遍历 - 后序遍历
 * 参 数：
 *      root：要遍历的树
 * 返回值：
 *      无 
 **/
void nonTraversal_PostOrder(BiTNode *root)
{
    if (root == NULL)
        return;
    // 创建一个栈
    LinkStack *stack = fLinkStack.create();
    BiTNode *top = root, *temp = NULL;
    // 将根节点入栈
    fLinkStack.push(stack, root);
    // 判断栈是否为空
    while (fLinkStack.length(stack) > 0)
    {
        // 获取栈顶元素，并判断是否有左右孩子
        top = fLinkStack.top(stack);

        // 不存在左右孩子，表示此节点为叶子节点
        // 根据栈顶元素与上次出栈的元素判断来确定是从左或者右孩子回退的
        if ((top->lchild == NULL && top->rchild == NULL) ||
            ((temp == top->lchild || temp == top->rchild) && temp != NULL))
        {
            printf("%c ", top->data);
            // 出栈，并记录下来用作下次栈顶元素的右孩子的判断
            temp = fLinkStack.pop(stack);
        }
        else // 存在左右孩子，入栈
        {
            if (top->rchild != NULL)
            {
                fLinkStack.push(stack, top->rchild);
            }
            if (top->lchild != NULL)
            {
                fLinkStack.push(stack, top->lchild);
            }
        }
    }

    // 销毁栈
    fLinkStack.destroy(stack);
}

/**
 * 功 能：
 *      二叉树的非递归遍历 - 后序遍历
 *          遍历顺序 ： 根节点 -> 右子树 -> 左子树
 *          采用 栈 进行翻转输出
 * 参 数：
 *      root：要遍历的树
 * 返回值：
 *      无 
 * 说 明：
 *      这种遍历放发类似于前序遍历，但是又不是先序遍历,大致思路就是：
 *          1.先将按照“根节点 -> 右孩子 -> 左孩子”的顺序进行遍历，然后将遍历要输出的节点保存起来
 *          2.然后将上面保存起来的数据进行翻转，然后输出就是了
 **/
void postOrder_Root_Right_Left_Stack(BiTNode *root)
{
    if (root == NULL)
        return;

    // 创建一个栈，用于遍历过程中记录节点
    LinkStack *stack1 = fLinkStack.create();
    // 在创建一个栈，用于在输出的节点的翻转
    LinkStack *stack2 = fLinkStack.create();

    // 将根节点进行入栈
    fLinkStack.push(stack1, root);
    // 判断栈是否为空
    while (fLinkStack.length(stack1) > 0)
    {
        // 出栈
        root = fLinkStack.pop(stack1);
        // 将出栈的节点作为新的根节点，判断出栈的节点是否存在左孩子或者右孩子
        if (root->lchild != NULL)
        {
            // 节点是存在左孩子或者右孩子，直接入栈
            fLinkStack.push(stack1, (LinkStackNode *)root->lchild);
        }
        // 将出栈的节点作为新的根节点，判断出栈的节点是否存在左孩子或者右孩子
        if (root->rchild != NULL)
        {
            // 节点是存在左孩子或者右孩子，直接入栈
            fLinkStack.push(stack1, (LinkStackNode *)root->rchild);
        }
        // 将原本要输出的节点保存到 栈 中
        // printf("%c ", root->data);
        fLinkStack.push(stack2, root);
    }
    // 将栈中的节点输出
    while (fLinkStack.length(stack2) > 0)
    {
        root = fLinkStack.pop(stack2);
        printf("%c ", root->data);
    }

    // 销毁栈
    fLinkStack.destroy(stack1);
    fLinkStack.destroy(stack2);
}

/**
 * 功 能：
 *      二叉树的非递归遍历 - 后序遍历
 *          遍历顺序 ： 根节点 -> 右子树 -> 左子树
 *          采用数组进行翻转输出
 * 参 数：
 *      root：要遍历的树
 * 返回值：
 *      无 
 * 
  * 说 明：
 *      这种遍历放发类似于前序遍历，但是又不是先序遍历,大致思路就是：
 *          1.先将按照“根节点 -> 右孩子 -> 左孩子”的顺序进行遍历，然后将遍历要输出的节点保存起来
 *          2.然后将上面保存起来的数据进行翻转，然后输出就是了
 **/
void postOrder_Root_Right_Left_Array(BiTNode *root)
{
    if (root == NULL)
        return;
    // 定义一个数组，用于保存遍历过程中要输出的节点的值
    unsigned char buf[512] = {0};
    // 定义一个变量，用于记录树的节点的个数
    int i = 0, cnt = 0;

    // 创建一个栈
    LinkStack *stack = fLinkStack.create();
    // 将根节点进行入栈
    fLinkStack.push(stack, root);
    // 判断栈是否为空
    while (fLinkStack.length(stack) > 0)
    {
        // 出栈
        root = fLinkStack.pop(stack);
        // 将出栈的节点作为新的根节点，判断出栈的节点是否存在左孩子或者右孩子
        if (root->lchild != NULL)
        {
            // 节点是存在左孩子或者右孩子，直接入栈
            fLinkStack.push(stack, (LinkStackNode *)root->lchild);
        }
        // 将出栈的节点作为新的根节点，判断出栈的节点是否存在左孩子或者右孩子
        if (root->rchild != NULL)
        {
            // 节点是存在左孩子或者右孩子，直接入栈
            fLinkStack.push(stack, (LinkStackNode *)root->rchild);
        }
        // 现在有两种做法
        // 1.先将要输出的字符写进一个数组或者什么内存中，然后在需要输出将这个数组进行翻转，就可以得到正常的后续遍历
        // 2.创建一个栈，然后将直将要输出的字符直接入栈，然后在需要输出时候在进行出栈就可。
        // 将原本要输出的节点保存到数组中
        // printf("%c ", root->data);
        buf[cnt++] = root->data;
    }
    // 将数组进行反向输出
    for (i = cnt; i > 0; i--)
        printf("%c ", buf[i - 1]);

    // 销毁栈
    fLinkStack.destroy(stack);
}

/**
 * 功 能：
 *      二叉树的非递归遍历 - 层序遍历
 * 参 数：
 *      root：要遍历的树
 * 返回值：
 *      无 
 **/
void nonTraversal_Level(BiTNode *root)
{
    if (root == NULL)
        return;
}

fNRTraversal traversal = {
    BiTree_Create,
    nonTraversal_Before,
    nonTraversal_Middle,
    nonTraversal_Post,
    nonTraversal_Level};
